package tree;
class Node{
    public int key;
    Node left;
    Node right;

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public Node(int key ){
        this.key = key;


    }
}

public class BinarySearchTree {
    //定义一个空树
    private Node root = null;

    //插入节点
    public void insert(int key) {
        //创建新节点
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return;
        }
        //普通的树，需要找到位置，然后再插入
        Node cur = root;//cur用来找待插入位置
        Node parent = null;//parent用来记录cur的父元素
        while (cur != null) {
            if (key < cur.key) {
                //如果待插入节点的key小于当前节点的key，则往左子树找
                parent = cur;
                cur = cur.left;

            } else if (key > cur.key) {
                //如果待插入节点的key大于当前节点的key，则往右子树找
                parent = cur;
                cur = cur.right;
            } else {
                //当前不允许有重复的key
                return;
            }
        }
        if (key < parent.key) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
    }

    //打印先序遍历
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.key + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    //打印中序遍历
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.key + " ");
        inOrder(node.right);
    }

    //打印后序遍历
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.key + " ");
    }

    //查找节点
    public Node find(int key) {
        if (root == null) {
            return null;
        }
        Node cur = root;//从root开始出发
        while (cur != null) {
            if (key == cur.key) {
                return cur;
            }
            //查找元素小于当前节点的左子树
            //然后就更新cur
            if (key < cur.key) {
                cur = cur.left;
                ;
            }
            //查找元素大于当前节点的右子树
            //然后就更新cur
            if (key > cur.key) {
                cur = cur.right;
            }
        }
        return null;
    }

    //删除搜索二叉树中的key，不存在什么都不做
    public void remove(int key) {
        if (root == null) {
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            } else {
                //进行删除
                removeNode(parent, cur);
                return;
            }
        }
    }
    //删除节点
    //考虑四种情况：
    //1.cur没有子树直接删除u
    //2cur只有左子树
    //3cur只有右子树
    //cur有左右子树

    private void removeNode(Node parent, Node cur) {
        //1.cur没有子树直接删除u
        if (cur.left == null && cur.right == null) {
            //如果cur是根节点，那就直接删除
            if (cur == root) {
                root = null;
            }
            //如果cur不是根节点，同时cur是parent的左子节点，那就把parent的左子节点设为null
            else if (cur == parent.left) {
                parent.left = null;
                //如果cur不是根节点，同时cur是parent的右子节点，那就把parent的右子节点设为null
            } else if (cur == parent.right) {
                parent.right = null;
            }
            return;
        }
        //2cur只有左子树
        if (cur.left != null && cur.right == null) {
            //如果cur是根节点，那就把左子树设为根节点
            if (cur == root) {
                cur = cur.left;
                root = cur;
            }
            //如果cur不是根节点，同时cur是parent的左子节点，那就把parent的左子节点设为左子树
            if (cur != root && cur == parent.left) {
                parent.left = cur.left;
            }
            //如果cur不是根节点，同时cur是parent的右子节点，那就把parent的右子节点设为左子树
            if (cur != root && cur == parent.right) {
                parent.right = cur.left;
            }
            return;
        }
      //3cur只有右子树
      if(cur.left==null&&cur.right!=null){
          //如果cur是根节点，那就把右子树设为根节点
          if(cur==root){
              cur=cur.right;
              root=cur;
          }
          //如果cur不是根节点，同时cur是parent的右子节点，那就把parent的右子节点设为右子树
          if(cur!=root&&cur==parent.right){
              parent.right=cur.right;
          }
          //如果cur不是根节点，同时cur是parent的左子节点，那就把parent的左子节点设为右子树
          if(cur!=root&&cur==parent.left){
              parent.left=cur.right;
          }
          return;
      }
      //cur有左右子树
        if(cur.left!=null&&cur.right!=null){
            //首先找到右子树的最小值
            Node minNode=cur.right;
            Node minParent=cur;
            while(minNode.left!=null){
                //更新minNode和minParent
                minParent=minNode;
                minNode=minNode.left;
            }
            //把minNode的值赋给cur
            cur.key=minNode.key;
            //如果minNode是右子树的最小值，那就直接删除minNode
            if(minNode==cur.right){
                minParent.left=null;
            }else{
                //如果minNode不是右子树的最小值，那就把minNode的右子树设为minNode的左子树
                minParent.left=minNode.right;
            }
            return;
        }

      }

    public static void main(String[] args) {
        BinarySearchTree tree=new BinarySearchTree();
        int[] arr={5,3,7,2,4,6,8};
         for(int i=0;i<arr.length;i++){
             tree.insert(arr[i]);
         }
//         System.out.println("先序遍历:");
//         tree.preOrder();
//         System.out.println();
//         System.out.println("中序遍历:");
//         tree.inOrder();
//         System.out.println();
//         System.out.println("后序遍历:");
//         tree.postOrder();
//         System.out.println();
        System.out.println(tree.find(8));
    }


}
